package com.wyp168.leetcode;


/**
 * @ClassName LongestPalindrome
 * @Description TODO  给定一个字符，找出最长回文字符串
 * @Author wyp168
 * @Date 2022/7/22 21:29
 */
public class LongestPalindrome {
    public static void main(String[] args) {
        String aa = "gphyvqruxjmwhonjjrgumxjhfyupajxbjgthzdvrdqmdouuukeaxhjumkmmhdglqrrohydrmbvtuwstgkobyzjjtdtjroqpyusfsbjlusekghtfbdctvgmqzeybnwzlhdnhwzptgkzmujfldoiejmvxnorvbiubfflygrkedyirienybosqzrkbpcfidvkkafftgzwrcitqizelhfsruwmtrgaocjcyxdkovtdennrkmxwpdsxpxuarhgusizmwakrmhdwcgvfljhzcskclgrvvbrkesojyhofwqiwhiupujmkcvlywjtmbncurxxmpdskupyvvweuhbsnanzfioirecfxvmgcpwrpmbhmkdtckhvbxnsbcifhqwjjczfokovpqyjmbywtpaqcfjowxnmtirdsfeujyogbzjnjcmqyzciwjqxxgrxblvqbutqittroqadqlsdzihngpfpjovbkpeveidjpfjktavvwurqrgqdomiibfgqxwybcyovysydxyyymmiuwovnevzsjisdwgkcbsookbarezbhnwyqthcvzyodbcwjptvigcphawzxouixhbpezzirbhvomqhxkfdbokblqmrhhioyqubpyqhjrnwhjxsrodtblqxkhezubprqftrqcyrzwywqrgockioqdmzuqjkpmsyohtlcnesbgzqhkalwixfcgyeqdzhnnlzawrdgskurcxfbekbspupbduxqxjeczpmdvssikbivjhinaopbabrmvscthvoqqbkgekcgyrelxkwoawpbrcbszelnxlyikbulgmlwyffurimlfxurjsbzgddxbgqpcdsuutfiivjbyqzhprdqhahpgenjkbiukurvdwapuewrbehczrtswubthodv";
        System.out.println(longestPalindrome(aa));
    }

    public static String longestPalindrome(String s) {
        if (s.length() == 1) {
            return s;
        }
        String res = "";
        int maxLength = 0;

        //TODO  遍历所有子串，找出最大回文子串
        for (int i = 0; i <s.length(); i++) {
            if (s.length() - i > maxLength) {
                for (int j = i + 1; j <= s.length(); j++) {
                    String substring = s.substring(i, j);
                    if (substring.length() > maxLength) {
                        boolean isPalindrome = isPalindrome(substring);
                        if (isPalindrome) {
                            res = substring;
                            maxLength = res.length();
                        }
                    }
                }
            }
        }

        return res;
    }

    public static boolean isPalindrome(String subS) {
        if (subS.length() == 0) {
            return false;
        }
        char[] subSC = subS.toCharArray();
        int lIndex = 0;
        int rIndex = subS.length() - 1;

        while (lIndex <= rIndex) {
            if (subSC[lIndex] != subSC[rIndex]) {
                break;
            }
            lIndex ++;
            rIndex --;
        }

        if (lIndex <= rIndex) {
            return false;
        } else {
            return true;
        }
    }
}
